package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author zhangjy
 * @description 二叉树的后序遍历
 * @date 2025/3/5 14:43
 */
public class PostorderTraversal_145 {

    public static void main(String[] args) {
        PostorderTraversal_145 postorderTraversal145 = new PostorderTraversal_145();

        TreeNode nine = new TreeNode(9, null, null);
        TreeNode eight = new TreeNode(8, nine, null);
        TreeNode seven = new TreeNode(7, null, null);
        TreeNode six = new TreeNode(6, null, null);
        TreeNode five = new TreeNode(5, six, seven);
        TreeNode four = new TreeNode(4, null, null);
        TreeNode three = new TreeNode(3, null, eight);
        TreeNode two = new TreeNode(2, four, five);
        TreeNode one = new TreeNode(1, two, three);

        // 递归
        postorderTraversal145.postorderTraversal(one).forEach(System.out::println);
        System.out.println("----");
        // 栈
//        postorderTraversal145.postorderTraversal3(one).forEach(System.out::println);
        postorderTraversal145.postorderTraversal4(one).forEach(System.out::println);
    }

    /**
     * dmsxl（不太理解）；
     * 有一种简便解法，在前序遍历的基础上修改；还有一种迭代统一解法，在中序的基础上修改。
     */
    public List<Integer> postorderTraversal5(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        return res;
    }

    /**
     * 法二，完全参考官解
     */
    public List<Integer> postorderTraversal4(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        if (root == null) return vals;

        Stack<TreeNode> st = new Stack<>();
        TreeNode node = root, prev = null;
        while (!st.isEmpty() || node != null) {
            while (node != null) {
                // 左
                st.push(node);
                node = node.left;
            }

            // 弹出的栈顶元素，其左子树必访问完，但是右子树仍需判断
            node = st.pop();

            if (node.right == null || node.right == prev) {
                // 根
                // 右子树为NIL，或者前一个访问节点为其右子树；那么访问当前节点
                vals.add(node.val);
                prev = node;
                // 置为null，便于继续出栈
                node = null;
            } else {
                // 右
                // 右子树非空且尚未被访问；栈顶元素再次入栈（保证左右中顺序），然后访问右子树
                st.push(node);
                node = node.right;
            }

        }
        return vals;
    }

    /**
     * 法一，参考官解（按后序的左右中顺序）；
     */
    public List<Integer> postorderTraversal3(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        if (root == null) return vals;

        Stack<TreeNode> st = new Stack<>();
        TreeNode node = root, prev = null, pop;
        while (!st.isEmpty() || node != null) {
            while (node != null) {
                // 左
                st.push(node);
                node = node.left;
            }
            // 弹出的栈顶元素，其左子树必访问完，但是右子树仍需判断
            pop = st.pop();

            if (pop.right != null && pop.right != prev) {
                // 右
                // 右子树非空且尚未被访问；栈顶元素再次入栈（保证左右中顺序），然后访问右子树
                st.push(pop);
                node = pop.right;
            } else {
                // 根
                // 右子树为NIL，或者前一个访问节点为其右子树；那么访问当前节点
                vals.add(pop.val);
                prev = pop;
            }

        }
        return vals;

        // 错误解法；无法保证右节点和已经访问过左右的父节点 不重复入栈
        // 如[1,2,3,4,5,null,6]，2的右节点5怎么才能不重复入栈？？？
        // 对于中序遍历，栈弹出节点时，其整个左子树已经访问完成，根据左中右顺序，此时可以访问根，再访问右；
        // 但是后序遍历，栈弹出时，只保证左子树访问完成，但是右子树未知，根据左右中顺序，此时不一定能访问根，要根据右子树是否访问来决定。
//        List<Integer> vals = new ArrayList<>();
//        if (root == null) return vals;
//
//        Stack<TreeNode> st = new Stack<>();
//        TreeNode node = root, pop;
//        boolean popFlag = false;
//        while (!st.isEmpty() || node != null) {
//            while (node != null) {
//                // 左
//                st.push(node);
//                node = node.left;
//            }
//            // 右
//            pop = st.pop();
//            node = pop.right;
//
//            // 根
//            if (node != null && !popFlag) {
//                st.push(pop);
//                // 根节点只重复入栈一次，处理完其右子树后不用再次入栈
//                popFlag = true;
//            } else {
//                popFlag = false;
//            }
//            // 左右已经处理完
//            if (node == null || popFlag) vals.add(pop.val);
//        }
//        return vals;
    }

    /**
     * 官解（官解不是左右中顺序）
     */
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        if (root == null) return vals;

        Stack<TreeNode> st = new Stack<>();
        TreeNode node = root, prev = null, pop;
        while (!st.isEmpty() || node != null) {
            while (node != null) {
                // 左
                st.push(node);
                node = node.left;
            }
            // 弹出的栈顶元素，其左子树必访问完，但是右子树仍需判断
            pop = st.pop();

            if (pop.right == null || prev == root.right) {
                // 根
                // 右子树为NIL，或者前一个访问节点为其右子树；那么访问当前节点
                vals.add(pop.val);
                prev = pop;
            } else {
                // 右
                // 右子树非空且尚未被访问；栈顶元素再次入栈（保证左右中顺序），然后访问右子树
                st.push(pop);
                node = pop.right;
            }

        }
        return vals;
    }

    /**
     * 递归
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        postorder(root, vals);
        return vals;
    }

    public void postorder(TreeNode root, List<Integer> vals) {
        // 1.返回值、入参：
        // 无返回值；入参：node、记录后序遍历顺序节点值的集合vals；
        // 2.终止条件：当前节点node == null
        if (root == null) return;

        // 3.单层逻辑：左—>右—>根顺序，记录节点值val
        // 先按顺序遍历本层（左—>右），再记录每一层根节点的val
        postorder(root.left, vals);
        postorder(root.right, vals);
        vals.add(root.val);
    }

}
